import java.util.*;

public class Main{
    public static void main(String[] args) {
        int num = 10;// 200000000;
        byte[][] bytes = arr(num);
        for (int i=0;i<num;i++){
            System.out.println(convert(bytes[i]));
        }
        System.out.println();
        quickSort(bytes,0,num-1);
        for (int i=0;i<num;i++){
            System.out.println(convert(bytes[i]));
        }
    }

    /**
     * 随机生成2亿个整数，每个数的取值范围在0~15000000之间，2亿 x 3 字节存储
     * @param num  整数个数
     * @return
     */
    public static byte[][] arr(int num) {
        Random random = new Random(1);
        // 每个byte占一个字节，三个byte可存24位
        byte[][] bytes = new byte[num][3];
        int temp;
        for(int i=0;i<num;i++){
            temp = random.nextInt(15000000);
            String temps = Integer.toBinaryString(temp);
            StringBuilder s = new StringBuilder();
            for(int k=temps.length();k<24;k++){
                s.append("0");
            }
            s.append(temps);
            int startP = 0;
            for(int j=0;j<3;j++){
                String s1 = s.substring(startP,startP+=8);
                bytes[i][j] = (byte)Integer.parseInt(s1,2);
            }
        }
        return bytes;
    }

    /**
     * 将byte数组存储的24位整数转换回来
     * @param bytes
     * @return
     */
    public static int convert(byte[] bytes){
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<3;i++){
            int b = bytes[i] & 0xFF;
            String te = Integer.toBinaryString(b);
            if (te.length()<8){
                    for(int x=0;x<8-te.length();x++){
                        sb.append("0");
                    }
                }
            sb.append(te);
        }
        return Integer.parseInt(sb.toString(),2);
    }

    /**
     * 快排
     * @param arr
     * @param low
     * @param high
     */
    private static void quickSort(byte[][] arr, int low, int high) {

        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);

            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            //quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }

    }

    private static int getIndex(byte[][] arr, int low, int high) {
        // 基准数据
        byte[] tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && convert(arr[high]) >= convert(tmp)) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && convert(arr[low]) <= convert(tmp)) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = tmp;
        // 返回tmp的正确位置
        return low;
    }

}
